package com.zac.coroutine.algorithm.leetcode.array

/**
 * author zac
 * date 2024/11/11
 *605. 种花问题
 * 已解答
 * 简单
 * 假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
 * 给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false 。
 * 示例 1：
 *
 * 输入：flowerbed = [1,0,0,0,1], n = 1
 * 输出：true
 * 示例 2：
 *
 * 输入：flowerbed = [1,0,0,0,1], n = 2
 * 输出：false
 *
 *
 * 提示：
 *
 * 1 <= flowerbed.length <= 2 * 104
 * flowerbed[i] 为 0 或 1
 * flowerbed 中不存在相邻的两朵花
 * 0 <= n <= flowerbed.length
 */
class Text16 {
    companion object {
        @JvmStatic
        fun main(args: Array<String>) {
            println(
                " 能种吗?${
                    canPlaceFlowers2(
                        arrayOf(
                            1,0,0,0,1,0,0
                        ).toIntArray(), 2
                    )
                }"
            )
        }

        /**
         * 官方题解
         */
        fun canPlaceFlowers2(flowerbed: IntArray, n: Int): Boolean {
            if (n == 0) return true
            var flower = n
            val f = IntArray(flowerbed.size + 2)

            System.arraycopy(flowerbed, 0, f, 1, flowerbed.size)

            for (i in 1 until f.size - 1) {
                if (f[i - 1] == 0 && f[i] == 0 && f[i + 1] == 0) {
                    f[i] = 1
                    flower -= 1
                    if (flower <= 0) {
                        return true
                    }
                }
            }
            return false
        }


        /**
         * 自己写的 太辣鸡了
         */
        fun canPlaceFlowers(flowerbed: Array<Int>, n: Int): Boolean {
            if (flowerbed.size == 1 && flowerbed[0] == 0 && n == 1) return true
            if (flowerbed.size == 2 && flowerbed[0] == 0 && flowerbed[1] == 0 && n == 1) return true
            var from = 0
            val map = HashMap<Int, Int>()
            for ((index, i) in flowerbed.withIndex()) {
                if (i == 0) {
                    if (index == 0) {
                        from = 2
                    } else {
                        from += 1
                        if (index == flowerbed.size - 1) {
                            from += 1
                            var saved = map[from]
                            if (saved != null) {
                                saved += 1
                            } else {
                                saved = 1
                            }
                            map[from] = saved
                            from = 0
                        }
                    }
                } else {
                    if (index != 0) {
                        var saved = map[from]
                        if (saved != null) {
                            saved += 1
                        } else {
                            saved = 1
                        }
                        map[from] = saved
                        from = 0
                    }
                }
            }
            var sum = 0
            map.forEach { (t, u) ->
                var emptyNum = t
                if (emptyNum > 2) {

                    if (emptyNum % 2 == 0) {
                        emptyNum -= 1
                    }
                    if (emptyNum == 3) {
                        sum += u
                        if (sum >= n) {
                            return@forEach
                        }
                    } else {
                        val flower = (emptyNum - 3) / 2
                        sum += flower * u + 1
                        if (sum >= n) {
                            return@forEach
                        }
                    }
                }

            }
            return sum >= n
        }
    }
}